#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<queue>
using namespace std;
typedef struct Tnode{
    char data;
    int h;
    struct Tnode *left,*right;
}*tree;
int max(int a,int b){
    return a>b?a:b;
}
tree newNode(char data){
    tree node=(tree)malloc(sizeof(struct Tnode));
    node->data=data;
    node->left=NULL;
    node->right=NULL;
    return node;
}
int height(tree node){
    if(node==NULL)
        return 0;
    return 1+max(height(node->left),height(node->right));
}
int getBalanceFactor(tree node){
    return height(node->left)-height(node->right);
}
tree rightRotate(tree y){
    /*
     * 树的结构示意图
            y node
           / \
          x   0
         / \
    val 0+1 0
    */
    tree x=y->left;
    tree xl=x->left;
    // 旋转
    x->left=y;
    y->right=xl;

    x->h=height(x);
    y->h=height(y);
    // 返回旋转后的最小子树的根节点
    return x;
}
tree leftRotate(tree y){
    /*
     * 树的结构示意图
            y node
           / \
          0   x
             / \
            0   0+1 val
    */
    tree x=y->right;
    tree xl=x->left;

    x->left=y;
    y->right=xl;

    x->h=height(x);
    y->h=height(y);
    return x;
}
tree createTree(tree root,char data){
    if(root==NULL)
        return newNode(data);
    if(data<root->data){
        root->left=createTree(root->left,data);
    }
    if(data>root->data){
        root->right=createTree(root->right,data);
    }
    root->h=height(root);
    int bf=getBalanceFactor(root);
    // LL
    if(bf>1&&root->left->data>data){
        return rightRotate(root);
    }
    // RR
    if(bf<-1&&root->right->data<data){
        return leftRotate(root);
    }
// LR
    if(bf>1&&root->left->data<data){
        root->left=leftRotate(root->left);
        return rightRotate(root);
    }
    // RL
    if(bf<-1&&root->left->data<data){
        root->right=rightRotate(root->right);
        return leftRotate(root);
    }
    return root;
}
void PreOrder_Iterative(tree root){
    if(root==NULL)
        return;
    stack<tree> s;
    s.push(root);
    while(!s.empty()){
        tree node=s.top();
        printf("%c ",node->data);
        s.pop();
        if(node->right) s.push(node->right);
        if(node->left)  s.push(node->left);
        
    }
}
int maxWidth(tree root){
    if(root==NULL)
        return 0;
    queue<tree> q;
    int max=0;
    q.push(root);
    while(!q.empty()){
        int width=q.size();
        for(int i=0;i<width;i++){
            tree node=q.front();
            q.pop();
            if(node->left)  q.push(node->left);
            if(node->right) q.push(node->right);
        }
        max=max>width?max:width;
    }
    return max;
}
int main(){
    tree root = NULL;
	int array[6] = { 'a','b','c','d','e','f'};
	for (int i = 0;i < 6;i++)
	{
		root=createTree(root, array[i]);
	}
    /*
     * 树的结构如下:
        d
      /   \
     b     e
    /  \    \
   a    c    f
    */ 
    printf("\n先序非递归:");
    PreOrder_Iterative(root);
    printf("\n最大宽度:%d",maxWidth(root));
    return 0;
}